package com.wangp.mywrite.coding.NextGreaterElement;

import java.util.*;

/**
 * @author tooStronger
 * @date 2022/7/3
 */
public class NextGreaterElementI {


    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
           int j = 0;
           while(nums1[i] != nums2[j]){
               j++;
           }
            int k = j+1;
           while(k < nums2.length && nums1[i] > nums2[k]){
               k++;
           }
           ans[i] = k < nums2.length ? nums2[k] : -1;
        }
        return ans;
    }


    public int[] nextGreaterElementLevel(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        // 使用 map 存储当前没有比更大的数
        Map<Integer,Integer> map = new HashMap<>();
        // 使用单调栈，寻找数字有没有更大的
        Deque<Integer> deque = new ArrayDeque<>();
        // 遍历 nums2
        for (int i = nums2.length - 1; i >= 0 ; i--) {
            int num = nums2[i];
            while(!deque.isEmpty() &&  num >= deque.peek()){
                deque.pop();
            }
            map.put(num,deque.isEmpty()?-1:deque.peek());
            deque.push(num);
        }
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }

    public static void main(String[] args) {

//        int[] ans = new NextGreaterElementI().nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
//        int[] ans = new NextGreaterElementI().nextGreaterElement(new int[]{3,1,5,7,9,2,6}, new int[]{1,2,3,5,6,7,9,11});
        int[] ans = new NextGreaterElementI().nextGreaterElementLevel(new int[]{3,1,5,7,9,2,6}, new int[]{1,2,3,5,6,7,9,11});
        System.out.println(Arrays.toString(ans));
    }

}
